//
//  Problem238.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 238. 除自身以外数组的乘积
 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

 示例:
     输入: [1,2,3,4]
     输出: [24,12,8,6]

 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
 */
@objcMembers class Problem238: NSObject {
    func solution() {
        print(productExceptSelfClear([1,2,3,4]))
    }
    
    /*
     前缀乘积 后缀乘积
     */
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        let n = nums.count
        var leftSum = Array(repeating: 0, count: n)
        leftSum[0] = nums[0]
        for i in 1..<n {
            leftSum[i] = leftSum[i-1] * nums[i]
        }
        print(leftSum)
        
        var rightSum = Array(repeating: 0, count: n)
        rightSum[n-1] = nums[n-1]
        for i in (0..<n-1).reversed() {
            rightSum[i] = rightSum[i+1] * nums[i]
        }
        print(rightSum)
        
        var result:[Int] = Array(repeating: 0, count: n)
        result[0] = rightSum[1]
        result[n-1] = leftSum[n-2]
        for i in 1..<n-1 {
            result[i] = leftSum[i-1] * rightSum[i+1]
        }
        return result
    }
    
    /*
     节省空间，利用结果数组来存储left
     */
    func productExceptSelfClear(_ nums: [Int]) -> [Int] {
        let n = nums.count
        var result = Array(repeating: 0, count: n)
        result[0] = nums[0]
        for i in 1..<n-1 {
            result[i] = result[i-1] * nums[i]
        }
        
        result[n-1] = result[n-2]
        var last = nums[n-1]
        for i in (1..<n-1).reversed() {
            result[i] = result[i-1] * last
            last *= nums[i]
        }
        result[0] = last
        
        return result
    }
}
